import java.util.HashMap;
import java.util.Map;

class Solution {
//    给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
//    示例 1:
//    输入: nums = [0,1]
//    输出: 2
//    说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
//    示例 2:
//    输入: nums = [0,1,0]
//    输出: 2
//    说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
    public int findMaxLength(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            if(nums[i] == 0){
                dp[i] = -1;
            }else{
                dp[i] = 1;
            }
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < len; i++){
            //前缀和
            sum += dp[i];
            //找到了要更新结果
            if(map.get(sum) != null){
                if(ret < i - map.get(sum)){
                    ret = i - map.get(sum);
                }
            }else{
                map.put(sum, i);
            }
        }
        return ret;
    }
}